package top.likeqc.leetcode.editor.cn;

import java.util.Stack;

/**
 * @see <a href="https://leetcode.cn/problems/reorder-list">143. 重排链表</a>
 */
public class ReorderList {
    public static void main(String[] args) {
        Solution solution = new ReorderList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        // 使用尽管时间复杂度一样，但使用寻找链表中点 + 链表逆序 + 合并链表的方法速度会更快
        // 因为图示代码操作了栈结构，多操作了一种数据结构
        public void reorderList(ListNode head) {
            int length = 1;
            Stack<ListNode> stack = new Stack<>();
            ListNode pNode = head, stackNode;
            
            stack.push(pNode);
            while ((pNode = pNode.next) != null) {
                length++;
                stack.push(pNode);
            }
            
            stackNode = stack.pop();
            pNode = head;
            while (true) {
                // 奇数情况结束标志
                if (pNode.equals(stackNode)) {
                    pNode.next = null;
                    break;
                }
                // 偶数情况结束标志
                if (pNode.next.equals(stackNode)) {
                    pNode.next = stackNode;
                    stackNode.next = null;
                    break;
                }
                
                stackNode.next = pNode.next;
                pNode.next = stackNode;
                
                pNode = stackNode.next;
                stackNode = stack.pop();
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
    
    
    public class ListNode {
        int val;
        ListNode next;
        
        ListNode() {
        }
        
        ListNode(int val) {
            this.val = val;
        }
        
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}